package com.gxc.array;

/**
 *34. 在排序数组中查找元素的第一个和最后一个位置
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
 * 请你找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 */
public class SearchRange {

    public static void main(String[] args) {
        print(handle(new int[]{5,7,7,8,8,10}, 8));
        print(handle(new int[]{5,7,7,8,8,10}, 6));
        print(handle(new int[]{}, 0));
    }

    public static int[] handle(int[] nums, int target) {
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if (nums.length == 0 || nums[0]>target || nums[nums.length-1]<target) return res;

        int l = nums.length;
        int start = start(nums, 0, l-1, target);
        int end = end(nums, 0, l-1, target);

        res[0] = start;
        res[1] = end;
        return res;
    }

    private static int start(int[] nums, int s, int e, int target) {
        if (s == e) return nums[s] == target ?s:-1;

        int mid = s + (e-s)/2;
        if (target == nums[mid]) {
            int start = start(nums, s, mid, target);
            return start == -1?mid:start;
        } else if (target>nums[mid]) {
            return start(nums, mid+1, e, target);
        } else {
            return start(nums, s, mid, target);
        }
    }

    private static int end(int[] nums, int s, int e, int target) {
        if (s == e) return nums[s] == target ?s:-1;

        int mid = s + (e-s)/2;
        if (target == nums[mid]) {
            int end = end(nums, mid+1, e, target);
            return end == -1?mid:end;
        } else if (target>nums[mid]) {
            return end(nums, mid+1, e, target);
        } else {
            return end(nums, s, mid, target);
        }
    }

    public static void print(int[] num) {
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");
        }
        System.out.println("");
    }

    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int leftIdx = binarySearch(nums, target, true);
            int rightIdx = binarySearch(nums, target, false) - 1;
            if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
                return new int[]{leftIdx, rightIdx};
            }
            return new int[]{-1, -1};
        }

        public int binarySearch(int[] nums, int target, boolean lower) {
            int left = 0, right = nums.length - 1, ans = nums.length;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] > target || (lower && nums[mid] >= target)) {
                    right = mid - 1;
                    ans = mid;
                } else {
                    left = mid + 1;
                }
            }
            return ans;
        }
    }

}
